#include<iostream>
#include<vector>

using namespace std;

//class Solution1{
//public:
//    int search(vector<int>& nums, int target) {
//        int begin = 0, end = nums.size() - 1;
//        while (begin <= end)
//        {
//            int pos = (begin + end) / 2;
//            if (nums[pos] > target) {
//                end = pos - 1;
//            }
//            else if (nums[pos] < target) {
//                begin = pos + 1;
//            }
//            else {
//                return pos;
//            }
//        }
//        return -1;
//    }
//};
int search(vector<int>& nums, int target, int begin, int end)
{
    while (begin <= end)
    {
        int pos = (begin + end) / 2;
        if (nums[pos] > target) {
            end = pos - 1;
        }
        else if (nums[pos] < target) {
            begin = pos + 1;
        }
        else {
            int left = search(nums, target, begin, pos - 1);
            int right = search(nums, target, pos + 1, end);
            if (left < (nums.size() - 1) / 2) return left;
            else return right;
        }
    }
    return -1;
}
vector<int> searchRange(vector<int>& nums, int target) {
    int begin = 0, end = nums.size() - 1;
    int pos = (begin + end) / 2;
    int left = search(nums, target, begin, pos-1);
    int right = search(nums, target, pos+1, end);
    vector<int> v;
    v.push_back(left);
    v.push_back(right);
    return v;

}



int main()
{
    vector<int> v({5, 7, 7, 8, 8, 10});
    searchRange(v, 8);
    return 0;
}